The invention relates generally to indexing and locating data and more specifically to indexing and locating key frames in variable-frame-length data.
Multimedia data is often stored in formats that reduce memory and bandwidth requirements. For example, video data is typically organized in frames. A frame provides an image which, when displayed in sequence with other images, gives the video data the ability to portray motion. While frames of video data could be stored and transmitted as frames of fixed length with each frame including all data needed to display that frame, such an approach tends to be inefficient and increases memory and bandwidth requirements.
Since images are often quite similar from frame-to-frame, video data from one frame, referred to as a key frame, may be utilized to reduce the amount of video data that needs to be stored and transmitted to display nearby frames. While the key frame includes sufficient video data to display the image it represents without reference to other frames, the nearby frames may contain much less video data since that video data may be combined with the video data of the key frame to display the nearby frames. Since the key frames and the nearby frames (non-key-frames) contain varying amounts of video data, the frames vary in length. A video format, for example, a Moving Picture Experts Group (MPEG) video format, is thus considered to be a variable-frame-length data format.
Variable-frame-length data formats may be advantageous in that minimal necessary frame lengths may be used. However, variable-frame-length data, by definition, results in loss of predictability of frame-to-frame distances. While this is not problematic when frames are being processed in consecutive sequence in their normal direction (e.g. forward), the lack of predictability can cause errors and complication when attempting to process the frames in a non-consecutive sequence or in a reverse direction. For example, providing fast forward and rewind functions usually involves playing back a frame, skipping several frames, playing back another frame, skipping more frames, and so on.
To obtain minimal necessary frame lengths in the variable-frame-length data, some frames (e.g., non-key-frames) are expressed with reference to other frames (e.g., key frames). The key frames are frames that contain sufficient information to be presented without reference to other frames. While key frames needed to interpret non-key frames may be readily available when frames are processed in a consecutive sequence in their normal direction (e.g., during normal playback), interpreting the non-key frames would not be possible if the key frames were skipped over during fast forward or rewind functions. Thus, fast forward and rewind functions usually rely on playback of selected key frames, skipping over all non-key frames.
Techniques have been developed to index frames and aid in locating frames. However, these techniques usually require information about the entire sequence of frames being indexed before the indexing may be performed. This requirement is not satisfactory for processing streaming data, where information about subsequently occurring frames in the stream is not known until the occurrence of those subsequently occurring frames. Thus, using such existing techniques, indexing of the stream would have to be suspended until the entire stream has been received. Also, sufficient memory resources to process the entire stream would be required.
Also, existing techniques associate indexing information only with certain frames, such as key frames, not with other frames, such as non-key-frames. Thus, use of the indexing information may be made only after a key frame has been located, not at any arbitrary frame in the sequence.
Thus, a method and apparatus is needed that allows indexing and locating key frames in streaming and variable-frame-length data. Furthermore, a technique is needed that allows location of desired key frames from any arbitrary frame in a sequence.